#include <stdio.h>
#include <float.h>
#include <math.h>
#include <time.h>
#include <sys/time.h>
#include <list>
#include <vector>
#include <algorithm>

double dist(int,int);

const double time_limit = 2.03;
//const double time_limit = 1.90;
const bool use_time_limit = true;
const int k_2opt = 65;
const int k_3opt = 200;
double start_time;
struct timeval real_time;

struct Pos
{
    double x;
    double y;
};

struct Node
{
    Node* next;
    Node* prev;
    int value;
    bool forward;

    Node(int value)
    {
        this->value=value;
        forward = true;
    }

    Node* getNext()
    {
        return forward ? next : prev;
    }
    void setNext(Node* n)
    {
        if(forward) next = n;
        else prev = n;
    }

    Node* getPrev()
    {
        return !forward ? next : prev;
    }
    void setPrev(Node* n)
    {
        if(!forward) next = n;
        else prev = n;
    }
};

int n;
Pos* pos;
Node* sol_start;
Node** nodes;
double* dist_data;
std::list<std::pair<int,int> > *k_nearest;

void read_input()
{
    scanf ("%d",&n);
    pos = new Pos[n];
    dist_data = new double[n*n];
    nodes = new Node*[n];
    k_nearest = new std::list<std::pair<int,int> >[n];



    for(int i=0;i<n;i++)
    {
        scanf ("%le",&pos[i].x);
        scanf ("%le",&pos[i].y);
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            double x= pos[i].x - pos[j].x;
            double y= pos[i].y - pos[j].y;

            dist_data[j+i*n] = rint(sqrt(x*x+y*y));
        }
    }
}

void print_output(Node* start)
{
    Node* current = start;
    int length=0;
    do
    {
        printf("%d\n", current->value);
        length += dist(current->value, current->getNext()->value);
        current = current->getNext();
    } while(current != sol_start);

    //printf("tour length = %d\n", length);

}

int tour_length()
{
    Node* current = sol_start;
    int length=0;
    do
    {
        length += dist(current->value, current->getNext()->value);
        current = current->getNext();
    } while(current != sol_start);
    return length;
}

inline double dist(int i, int j)
{
    return dist_data[j+i*n];
}

void NN()
{
    bool* visited = new bool[n];

    visited[0]=true;
    sol_start = new Node(0);
    nodes[0] = sol_start;
    Node* current = sol_start;

    for(int sol_size=1;sol_size<n;sol_size++)
    {
        double min=DBL_MAX;
        int min_i=-1;

        for(int i=0;i<n;i++)
        {
            if(i!= current->value && visited[i]==false)
            {
                double d = dist(current->value,i);

                if(d < min)
                {
                    min = d;
                    min_i = i;
                }
            }
        }

        visited[min_i]=true;

        Node* n = new Node(min_i);
        nodes[min_i] = n;
        n->setPrev(current);
        current->setNext(n);

        current = current->getNext();
    }
    current->setNext(sol_start);
    sol_start->setPrev(current);

}

struct Edge
{
    Node* i;
    Node* j;
};

struct SetNode
{
    SetNode* parent;
    int rank;
    int value;
    SetNode(int value)
    {
        this->value = value;
        rank = 0;
        parent = this;
    }
};

SetNode* setFind(SetNode* x)
{
    if (x->parent != x)
    {
        x->parent = setFind(x->parent);
    }
    return x->parent;
}

void setUnion(SetNode* x, SetNode* y)
{
    SetNode* xRoot = setFind(x);
    SetNode* yRoot = setFind(y);

    if(xRoot == yRoot)
        printf("Error same set already\n");

    if (xRoot->rank < yRoot->rank)
    {
        xRoot->parent = yRoot;
    }
    else if (xRoot->rank > yRoot->rank)
    {
        yRoot->parent = xRoot;
    }
    else
    {
        yRoot->parent = xRoot;
        xRoot->rank = xRoot->rank + 1;
    }
}




inline bool edge_sort(const Edge& i, const Edge& j)
{
    return dist(i.i->value, i.j->value) < dist(j.i->value, j.j->value);
}

void greedy()
{
    std::list<Edge> edges;
	
    for(int i=0;i<n;i++)
    {
        nodes[i] = new Node(i);
        for(int j=0;j<i;j++)
        {
            Edge e;
            e.i = nodes[i];
            e.j = nodes[j];

			edges.push_back(e);
        }
    }

    edges.sort(edge_sort);

    SetNode** setNodes = new SetNode*[n];
    for(int i=0;i<n;i++)
    {
        setNodes[i] = new SetNode(i);
    }

    int count = 0;

    //printf("edges size = %i\n", edges.size());
    while(count < n-1)
    {
        //printf("count = %i\n", count);
        Edge e= edges.front();
        edges.pop_front();

		if((e.i->getNext() == NULL || e.i->getPrev() == NULL) && (e.j->getNext() == NULL || e.j->getPrev() == NULL))
        {
            if(setFind(setNodes[e.i->value]) != setFind(setNodes[e.j->value]))
            {
                setUnion(setNodes[e.i->value], setNodes[e.j->value]);
                //printf("adding edge with i = %i, j= %i\n", e.i->value, e.j->value);
                count++;

                if(e.i->getNext() == NULL)
                    e.i->setNext(e.j);
                else
                    e.i->setPrev(e.j);

                if(e.j->getPrev() == NULL)
                    e.j->setPrev(e.i);
                else
                    e.j->setNext(e.i);
            }
        }
    }

    Node* first = NULL;
    Node* second = NULL;

    for(int i=0;i<n;i++)
    {
        if(nodes[i]->getNext() == NULL)
        {
            //printf("added = %i\n", nodes[i]->value);
            if(first == NULL)
                first = nodes[i];
            else
                second = nodes[i];
        }
        else if(nodes[i]->getPrev() == NULL)
        {
            //printf("added = %i\n", nodes[i]->value);
            if(first == NULL)
                first = nodes[i];
            else
                second = nodes[i];
        }
    }

    if(first->getNext() == NULL) first->setNext(second);
    else first->setPrev(second);

    if(second->getNext() == NULL) second->setNext(first);
    else second->setPrev(first);

    Node* node = nodes[0];
    sol_start = nodes[0];

    while(true)
    {
        Node* next = node->getNext();
        //printf("node = %p next = %p\n", node, next);
        if(next->getNext() == node)
        {
            next->forward = !next->forward;
        }
        node = next;

        if(node == nodes[0]) break;
    }
}



void init_k_nearest()
{
    for(int node=0;node<n;node++)
    {
        int size = 0;
        for(int i=0;i<n;i++)
        {
            double d = dist(node,i);
            if(node != i)
            {
                /*bool inserted = false;
                for(std::list<std::pair<int,int> >::iterator it = k_nearest[node].begin();it != k_nearest[node].end();it++)
                {
                if(d < it->second)
                {
                k_nearest[node].insert(it, std::pair<int,int>(i,d));
                size++;
                if(size > k)
                {
                size--;
                k_nearest[node].pop_back();
                }
                inserted = true;
                break;
                }
                }
                if(!inserted && size < k)
                {
                k_nearest[node].push_back(std::pair<int,int>(i,d));
                size++;
                }
                */
                k_nearest[node].push_back(std::pair<int,int>(d,i));

            }
        }
        k_nearest[node].sort();
    }
}

void tour_validation(Node* node)
{
    bool visited[n];
    for(int i=0;i<n;i++)
    {
        visited[i] = false;
    }

    printf("tour starting in %d\n", node->value);
    int start = node->value;
    int count = 0;
    while(true)
    {
        if(start == node->value && count == n)
        {
            printf("tour is valid!\n");
            break;
        }
        else if(visited[node->value] == true)
        {
            printf("tour visited %d again, error detected!\n", node->value);
            exit(0);
            break;
        }
        else
        {
            visited[node->value] = true;
            //printf("tour visited %d\n", node->value);
            node = node->getNext();
            count++;
        }
    }
}

void swap(Node* n1, Node* n2)
{
    Node* temp = n1->getNext();
    Node* temp2 = n2->getNext();

    n1->setNext(n2);
    n2->setNext(n1);

    Node* n = n2;
    while(n != temp){
        n->forward = !n->forward;
        n = n->getNext();
    }
    temp->forward = !temp->forward;

    temp->setNext(temp2);
    temp2->setPrev(temp);
}

void swap3_t2(Node* n1, Node* n2, Node* n3)
{
    Node* a = n1;
    Node* b = n1->getNext();
    Node* c = n2;
    Node* d = n2->getNext();
    Node* e = n3;
    Node* f = n3->getNext();

    Node* n = a;
    while(n != f){
        n->forward = !n->forward;
        n = n->getNext();       
    }
    f->forward = !f->forward;

    c->setNext(a);
    a->setPrev(c);
    f->setNext(d);
    d->setPrev(f);
    e->setNext(b);
    b->setPrev(e);
}

void swap3_t3(Node* n1, Node* n2, Node* n3)
{
    Node* a = n1;
    Node* b = n1->getNext();
    Node* c = n2;
    Node* d = n2->getNext();
    Node* e = n3;
    Node* f = n3->getNext();

    Node* n = c;
    while(n != b){
        n->forward = !n->forward;
        n = n->getNext();       
    }
    b->forward = !b->forward;

    a->setNext(d);
    d->setPrev(a);
    e->setNext(c);
    c->setPrev(e);
    b->setNext(f);
    f->setPrev(b);
}

void swap3_t4(Node* n1, Node* n2, Node* n3)
{
    Node* a = n1;
    Node* b = n1->getNext();
    Node* c = n2;
    Node* d = n2->getNext();
    Node* e = n3;
    Node* f = n3->getNext();

    a->setNext(e);
    c->setNext(f);

    Node* n = e;
    while(n != d){
        n->forward = !n->forward;
        n = n->getNext();       
    }
    d->forward = !d->forward;

    e->setPrev(a);
    d->setNext(b);
    b->setPrev(d);
    f->setPrev(c);
}

void swap3_t5(Node* n1, Node* n2, Node* n3)
{
    Node* temp1 = n1->getNext();
    Node* temp2 = n2->getNext();
    Node* temp3 = n3->getNext();

    n1->setNext(temp2);
    n2->setNext(temp3);
    n3->setNext(temp1);

    temp1->setPrev(n3);
    temp2->setPrev(n1);
    temp3->setPrev(n2);
}


void two_OPT()
{
    int steps_since_last_improvement = 0;
    Node* n1 = sol_start->getNext();

    while(steps_since_last_improvement < n*n)
    {
        //gettimeofday(&real_time, NULL);
        //double time = real_time.tv_sec + ((double)real_time.tv_usec)/1000000.0;
        //if(time - start_time > time_limit && use_time_limit)
        //{
        //      return;
        //}


        Node* n2 = sol_start;
        do
        {
            if(n1 != n2)
            {
                double old_d1 = dist(n1->value, n1->getNext()->value);
                double old_d2 = dist(n2->value, n2->getNext()->value);
                double new_d1 = dist(n1->value, n2->value);
                double new_d2 = dist(n1->getNext()->value, n2->getNext()->value);

                if(new_d1+new_d2 < old_d1+old_d2)
                {
                    steps_since_last_improvement = 0;
                    swap(n1, n2);
                }
                //else
                //{
                //steps_since_last_improvement++;
                //}
            }
            steps_since_last_improvement++;
            n2 = n2->getNext();
        } while(n2 != sol_start);
        n1 = n1->getNext();
    }
}

void two_OPT_v2()
{
    bool swapped = true;

    while(swapped)
    {
        gettimeofday(&real_time, NULL);
        double time = real_time.tv_sec + ((double)real_time.tv_usec)/1000000.0;
        if(time - start_time > time_limit && use_time_limit)
        {
            return;
        }
        swapped = false;

        for(int i=0;i<n;i++)
        {
            int next = nodes[i]->getNext()->value;
            int d = dist(i, next);

            int count = 0;
            for(std::list<std::pair<int,int> >::iterator it = k_nearest[next].begin();it != k_nearest[next].end();it++)
            {
                if(count > k_2opt) break;
                count++;
                if(d > it->first)
                {
                    double old_d1 = dist(i, next);
                    double old_d2 = dist(it->second, nodes[it->second]->getNext()->value);
                    double new_d1 = dist(i, it->second);
                    double new_d2 = dist(next, nodes[it->second]->getNext()->value);

                    if(new_d1+new_d2 < old_d1+old_d2)
                    {
                        swap(nodes[i], nodes[it->second]);
                        swapped = true;

                        //break;
                        //printf("swap\n");
                        //tour_validation(sol_start);
                    }
                }
                else
                {
                    break;
                }
            }
        }
    }
}

void three_OPT_v2()
{
    bool swapped = true;

    while(swapped)
    {
        swapped = false;
        for(int i=0;i<n;i++)
        {
            int next = nodes[i]->getNext()->value;
            int distance = dist(i, next);

            gettimeofday(&real_time, NULL);
            double time = real_time.tv_sec + ((double)real_time.tv_usec)/1000000.0;
            if(time - start_time > time_limit && use_time_limit)
            {
                return;
            }
            int count =0;
            for(std::list<std::pair<int,int> >::iterator it = k_nearest[next].begin();it != k_nearest[next].end();it++)
            {
                if(count > k_3opt) break;
                count++;
				
				bool temp = false;
				
                if(distance > it->first)
                {
					
                    Node* j = nodes[it->second];
                    while(j->value != i)
                    {
                        /*if(i != it->second && i!= nodes[it->second]->getNext()->value && i != j->value && i != j->getNext()->value && 
                        next != it->second && next != nodes[it->second]->getNext()->value && next != j->value && next != j->getNext()->value &&
                        it->second != j->value && it->second != j->getNext()->value &&
                        nodes[it->second]->getNext()->value != j->value && nodes[it->second]->getNext()->value != j->getNext()->value)*/
                        if(nodes[it->second]->getNext()->value != j->getNext()->value)
                        {
                            const int a = i;
                            const int b = next;
                            const int c = it->second;
                            const int d = nodes[it->second]->getNext()->value;
                            const int e = j->value;
                            const int f = j->getNext()->value;

                            const double t1_d1 = dist(a, b);
                            const double t1_d2 = dist(c, d);
                            const double t1_d3 = dist(e, f);
                            const double t1_sum = t1_d1+t1_d2+t1_d3;

                            const double t2_d1 = dist(a, c);
                            const double t2_d2 = dist(b, e);
                            const double t2_d3 = dist(d, f);
                            const double t2_sum = t2_d1+t2_d2+t2_d3;

                            const double t3_d1 = dist(a, d);
                            const double t3_d2 = dist(b, f);
                            const double t3_d3 = dist(c, e);
                            const double t3_sum = t3_d1+t3_d2+t3_d3;

                            const double t4_d1 = dist(a, e);
                            const double t4_d2 = dist(b, d);
                            const double t4_d3 = dist(c, f);
                            const double t4_sum = t4_d1+t4_d2+t4_d3;

                            const double t5_d1 = dist(a, d);
                            const double t5_d2 = dist(c, f);
                            const double t5_d3 = dist(e, b);
                            const double t5_sum = t5_d1+t5_d2+t5_d3;


                            //T5 
                            if(t5_sum < t1_sum)
                            {
                                //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                                //tour_validation(sol_start);
                                swap3_t5(nodes[i], nodes[it->second], j);
                                //tour_validation(sol_start);
                                swapped = true;
                                //next = nodes[i]->getNext()->value;
                                //distance = dist(i, next);
								temp = true;
                                break;
                            }

                            //T3
                            if(t3_sum < t1_sum)
                            {
                                //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                                //tour_validation(sol_start);
                                swap3_t3(nodes[i], nodes[it->second], j);
                                //tour_validation(sol_start);
                                swapped = true;
                                //next = nodes[i]->getNext()->value;
                                //distance = dist(i, next);
								temp = true;
                                break;
                            }

                            //T4
                            if(t4_sum < t1_sum)
                            {
                                //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                                //tour_validation(sol_start);
                                swap3_t4(nodes[i], nodes[it->second], j);
                                //tour_validation(sol_start);
                                swapped = true;
                                //next = nodes[i]->getNext()->value;
                                //distance = dist(i, next);
								temp = true;
                                break;
                            }

                            if(t2_sum < t1_sum)
                            {
                                //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                                //tour_validation(sol_start);
                                swap3_t2(nodes[i], nodes[it->second], j);
                                //tour_validation(sol_start);
                                swapped = true;
                                //next = nodes[i]->getNext()->value;
                                //distance = dist(i, next);
								temp = true;
                                break;
                            }
                            /*
                            //T2 best optimization
                            if(t2_sum < t1_sum && t2_sum < t3_sum && t2_sum < t4_sum && t2_sum < t5_sum)
                            {
                            //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                            //tour_validation(sol_start);
                            swap3_t2(nodes[i], nodes[it->second], j);
                            //tour_validation(sol_start);
                            swapped = true;
                            next = nodes[i]->getNext()->value;
                            d = dist(i, next);
                            break;
                            }
                            */
                            /*
                            //T3 best optimization
                            if(t3_sum < t1_sum && t3_sum < t2_sum && t3_sum < t4_sum && t3_sum < t5_sum)
                            {
                            //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                            //tour_validation(sol_start);
                            swap3_t3(nodes[i], nodes[it->second], j);
                            //tour_validation(sol_start);
                            swapped = true;
                            next = nodes[i]->getNext()->value;
                            d = dist(i, next);
                            break;
                            }
                            */
                            /*
                            //T4 best optimization
                            if(t4_sum < t1_sum && t4_sum < t2_sum && t4_sum < t3_sum && t4_sum < t5_sum)
                            {
                            //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                            //tour_validation(sol_start);
                            swap3_t4(nodes[i], nodes[it->second], j);
                            //tour_validation(sol_start);
                            swapped = true;
                            next = nodes[i]->getNext()->value;
                            d = dist(i, next);
                            break;
                            }
                            */
                            /*
                            //T5 best optimization
                            if(t5_sum < t1_sum && t5_sum < t2_sum && t5_sum < t3_sum && t5_sum < t4_sum)
                            {
                            //printf("preswap %i->%i, %i->%i, %i->%i\n", i, next, it->first,  nodes[it->first]->getNext()->value, j->value, j->getNext()->value);
                            //tour_validation(sol_start);
                            swap3_t5(nodes[i], nodes[it->second], j);
                            //tour_validation(sol_start);
                            swapped = true;
                            next = nodes[i]->getNext()->value;
                            d = dist(i, next);
                            break;
                            }
                            */
                        }
                        j = j->getNext();
                    }
                }
                else
                {
                    break;
                }
				
				if(temp) break;
            }
        }

    }
}


void three_OPT()
{
    int steps_since_last_improvement = 0;
    Node* n1 = sol_start->getNext();

    while(steps_since_last_improvement < n*n*n)
    {
        gettimeofday(&real_time, NULL);
        double time = real_time.tv_sec + ((double)real_time.tv_usec)/1000000.0;
        if(time - start_time > time_limit && use_time_limit)
        {
            return;
        }
        Node* n2 = n1->getNext();
        while(n2 != n1)
        {
            gettimeofday(&real_time, NULL);
            double time = real_time.tv_sec + ((double)real_time.tv_usec)/1000000.0;
            if(time - start_time > time_limit && use_time_limit)
            {
                return;
            }

            Node* n3 = n2->getNext();
            while (n3 != n1)
            {
                gettimeofday(&real_time, NULL);
                double time = real_time.tv_sec + ((double)real_time.tv_usec)/1000000.0;
                if(time - start_time > time_limit && use_time_limit)
                {
                    return;
                }

                if(n1 != n2 && n1 != n3 && n2 != n3 &&  n1 != n2->getNext() && n1 != n3->getNext() && 
                    n2 != n1->getNext() && n2 != n3->getNext() && n3 != n1->getNext() && n3 != n1->getNext())
                {
                    double old_d1 = dist(n1->value, n1->getNext()->value);
                    double old_d2 = dist(n2->value, n2->getNext()->value);
                    double old_d3 = dist(n3->value, n3->getNext()->value);

                    double new_d1 = dist(n1->value, n2->getNext()->value);
                    double new_d2 = dist(n2->value, n3->getNext()->value);
                    double new_d3 = dist(n3->value, n1->getNext()->value);

                    if(new_d1+new_d2+new_d3 < old_d1+old_d2+old_d3)
                    {
                        steps_since_last_improvement = 0;
                        //printf("preswap %i->%i, %i->%i, %i->%i\n", n1->value, n1->getNext()->value, n2->value, n2->getNext()->value, n3->value, n3->getNext()->value);
                        swap3_t5(n1, n2, n3);
                        //printf("postswap %i->%i, %i->%i, %i->%i\n", n1->value, n1->getNext()->value, n2->value, n2->getNext()->value, n3->value, n3->getNext()->value);
                        n2 = n1->getNext();
                        n3 = n2->getNext();
                        //tour_validation(sol_start);
                        continue;
                    }
                    else
                    {
                        steps_since_last_improvement++;
                    }
                }

                n3 = n3->getNext();
            }
            n2 = n2->getNext();
        }
        n1 = n1->getNext();
    }
}

Node* solve()
{

    //NN();
    greedy();
    init_k_nearest();
    two_OPT_v2();
    three_OPT_v2();

    return sol_start;
}

int main()
{
    gettimeofday(&real_time, NULL);
    start_time = real_time.tv_sec + ((double)real_time.tv_usec)/1000000.0;

    read_input();
    if(n == 1)
    {
        printf("0\n");
    }
    else
    {
        print_output(solve());
    }
    return 0;
}